1. Field of the Invention
The present invention relates to an improvement of data processing systems employing memory systems that utilize error checking and correcting systems. More particularly, it relates to systems for detecting the occurrence of data errors.
2. State of the Prior Art
One of the basic reasons for the rapid advancement of data processing has been the ongoing development of improved memory devices. Improvements of memory devices have included improvement of memory cells that are ever-reducing in size, while ever-increasing in the rate of performance. The reductions in size have been occasioned by manufacturing techniques. Particularly, integrated circuit manufacturing techniques have led to large capacity memories physically located in very compact structures.
While early data processing systems simply stored data either on fixed medium such as punched cards or punched paper tape, or in addressable storage, it was soon established that it was desirable to recognize the occurrence of errors within fixed groupings of data signals. In digital data processing systems operating on data words comprised of predetermined bit groupings, it became common to utilized an additional bit for parity determination. The use of parity systems allows the detection of errors but not the correction thereof.
Parity as an error detecting mechanism is known, and in binary systems requires only a single additional bit position for the bit groupings to be checked. The parity bit is then utilized to establish either an odd or even count of the ones or zeros in the bit grouping to be checked. It is, of course, apparent that multiple errors can be offsetting, and thereby defeat the parity check. Offsetting errors may allow erroneous data to be processed.
Data communication systems have been found to be particularly susceptible to occurrence of errors. Parity systems have been developed for data communication wherein the bit groupings are broken into subsets with a parity bit added for each subset for transmission. These additional parity bits render the likelihood of detecting errors more probable, but at the expense of the overhead of the additional bits having to be transmitted. In communication systems it was also early determined to be advantageous to be able to correct certain detected errors. Such systems normally included the coding of the data bits in predetermined formats with redundant check patterns such that multiple errors could be detected and corrected. Such encoding and decoding led to more reliable communication systems and allowed for the system to maintain its operable status in the face of certain types of intermittent failures.
Memory systems have increased in storage capacity and rate of operation, and the reliable operation of memory systems is basic to maintaining the integrity of data processing systems.
A technique was proposed for coding data permitting correction of single bit errors and detection of double bit errors, by R. W. Hamming in an article entitled "Error Detecting And Error Correcting Codes" in the Bell System Technical Journal, Volume 29, Pages 147 through 160 published April, 1950. Many memory systems have built upon this type of Error Correction Codes, hereinafter referred to as ECC. For example, U.S. Pat. No. 3,755,779, issued to Donald Walter Price sets forth a system for detecting and correcting single errors and includes apparatus for detecting unrelated double errors. Further examples of coding systems for providing single-bit error correction and double-bit error detection are described in U.S. Pat. No. 4,345,328 to Gary D. White; U.S. Pat. No. 4,077,028 to Albert S. Lui and Majid Arbab; U.S. Pat. No. 4,319,356 to James E. Kocol and David B. Schuck; U.S. Pat. No. 4,077,565 to Chester M. Nibby, Jr. and George J. Barlow; and U.S. Pat. No. 4,319,357 to Douglas C. Bossen.
The foregoing identified patents describe various types of systems that can code data bits with redundant check bits in various configurations, with the check bits being recorded in the memory system with the data bits. When the data bits are to be accessed, systems are described for reconstituting check bits from the data bits read, and thereafter performing a comparison to the check bits that were originally recorded. Syndrome bits are generated as a result of comparison of the reconstituted check bits to the check bits read from memory. The syndrome bits are decoded and a determination made as to which, if any, error bits are detected. Various types of circuitry are described for effecting the corrections that can be accommodated in the system. Many of the systems illustrated also describe error indicator circuitry for indicating the type of errors that were detected. It is to this latter feature that the subject invention is directed. The error indicator circuits in the prior art, as will be described in more detail below, characteristically translate the syndrome bits for providing indications as to the nature of the errors detected. Since this error indicating function occurs each time there is a memory read, it is desirable that the error indicator circuitry operate as fast as possible, that it minimize the number of circuits required to accomplish the error indication function, and that it minimize the loading of the circuitry that generates the syndrome bits.
In addition to the error detection and correction functions, it has developed that through-checking is desirable for detecting and isolating errors that occur as data is transferred through the system. Through-checking ECC systems for use with memory devices are described in U.S. patent application Ser. No. 354,340 entitled "Memory Through Checking System" by James H. Scheuneman, assigned to the assignee of the present invention and U.S. patent application Ser. No. 354,328 entitled "Error Correction Code Through Check System" by John R. Trost, also assigned to the assignee of the present invention.